00wi_hw4

3. 10 pts total. 7 for 2 right, 3 for 1 right.
    (a) True. If a location is 0, that means no words hashed to it are in the table, not only the word we are reading, but also the words that have the same hash value.
    (b) False. Hash collision. Since other words may also be hashed to that location, so a '1' in that location doesn't necessarily mean that the word we are reading is in the table
    (c) 300,008 bits -- 37501 bytes, or if the machine allocates memory on a 4-byte basis, the table takes 37504 bytes.

4. 10 pts total. 4pts - looking for the correct place to insert. 4 pts - pointer manipulation. 2pts - miscellaneous.
Insert(int age, int weight, PLIST_ENTRY ageList, PLIST_ENTRY weightList)
{
    PMYSTRUCT newStruct= new MYSTRUCT;
    newStruct->age = age;
    newStruct->weight = weight;

    //insert in age list
    for (PLIST_ENTRY pAge=ageList.FLink; pAge!=ageList; pAge=pAge.FLink)
    {
        PMYSTRUCT pMyStruct = CONTAINING_RECORD(pAge, MYSTRUCT, SortByAge);
        if (pMyStruct->age > age)
            break;
    }
    newStruct->SortByAge->FLink = pAge;
    newStruct->SortByAge->BLink = pAge->BLink;
    pAge->BLink->FLink = newStruct->SortByAge;
    pAge->BLink = newStruct->SortByAge;

    //insert in weight list
    for (PLIST_ENTRY pWeight=weightList.FLink; pWeight!=weightList; pWeight=pWeight.FLink)
    {
        PMYSTRUCT pMyStruct = CONTAINING_RECORD(pWeight, MYSTRUCT, SortByWeight);
        if (pMyStruct->weight> weight)
            break;
    }
    newStruct->SortByAge->FLink = pWeight;
    newStruct->SortByAge->BLink = pWeight->BLink;
    pWeight->BLink->FLink = newStruct->SortByWeight;
    pWeight->BLink = newStruct->SortByWeight;
}